package problem85_Maximal_Rectangle;

import java.util.Arrays;
import java.util.Stack;

public class Solution {
	public int maximalRectangle(char[][] matrix) {
		if(matrix.length==0)	return 0;
		int [][]height=new int[matrix.length][matrix[0].length];
		int max=0;
		for(int i=0;i<matrix.length;i++){
			for(int j=0;j<matrix[0].length;j++){
				if(matrix[i][j]=='1'){
					height[i][j]=(i==0?1:height[i-1][j]+1);
				}
			}
			max=Math.max(max, largestRectangleArea(height[i]));
		}
		return max;
    }
	
	private int largestRectangleArea(int[] height) {
		Stack<Integer> stack=new Stack<Integer>();
		height=Arrays.copyOf(height, height.length+1);	//make height[length]=0;
		int i=0,maxArea=0;
		while(i<height.length){
			if(stack.isEmpty()||height[i]>=height[stack.peek()]){
				stack.push(i++);
			}else{
				int tmp=stack.pop();
				maxArea=Math.max(maxArea,height[tmp]*(stack.isEmpty()?i:(i-1)-stack.peek()));
			}
		}
		return maxArea;
	}
}
